package com.LeetCode.doublePair;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 四数之和
 */
public class FourSum {

    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums == null || nums.length < 4)
            return res;

        Arrays.sort(nums);
        int len = nums.length;
        for(int i = 0; i < len - 3; i++){
            if(i > 0 && nums[i] == nums[i-1])
                continue;
            int min1 = nums[i] + nums[i+1] + nums[i+2] + nums[i+3];
            if(min1 > target)//如果最小的组合都没目标小，那就没戏了
                break;

            int max1 = nums[i] + nums[len-1] + nums[len-2] + nums[len-3];
            if(max1<target){//如果最大的组合都没目标大，那也没戏了
                continue;//这里是continue, 因为每次最大值都会变
            }

            //枚举第二个指针
            for(int j = i + 1; j<len - 2; j++){
                if(j > i + 1 && nums[j] == nums[j-1])
                    continue;

                int l = j + 1;
                int r = len - 1;

                int min = nums[i] + nums[j] + nums[l] + nums[l+1];
                if(min>target)
                    continue;

                int max = nums[i] + nums[j] + nums[r] + nums[r-1];
                if(max<target)
                    continue;


                while(l < r){
                    int curSum = nums[i] + nums[j] + nums[l] + nums[r];
                    if(curSum == target){
                        res.add(new ArrayList<>(Arrays.asList(nums[i],nums[j],nums[l],nums[r])));
                        l++;
                        while(l<r && nums[l] == nums[l-1]) l++;
                        r--;
                        while(l<r && nums[r] == nums[r+1]) r--;
                    }else if(curSum > target){
                        r--;
                    }else{
                        l++;
                    }
                }
            }

        }
        return res;
    }

    @Test
    public void test(){
        int[] arr = {1, 0, -1, 0, -2, 2};
        fourSum(arr,0).forEach(System.out::println);
    }
}
